第1关：熟悉Python中的list 任务描述 本关任务：编写一个能对 list 对象，进行插入、删除和修改的程序。 相关知识 为了完成本关任务，你需要掌握： 对 list 的随机访问； 如何“弹出” list 的第一个和最后一个元素； 如何向 list 添加数据。 对 list 的随机访问 随机访问就是指，能不能通过下标之类的索引，直接访问某一位置的元素。数据结构中，顺序表最主要的特点就是随机访问。 Python 中 list 的索引，只能是整数或者切片。通过整数访问，就和一些高级编程语言中的数组的访问类似，直接通过中括号里面加整数下标，来访问数据。但 Python 中整数下标是支持负数下标的，负数表示从 list 最后一个元素开始计算，如 -2 就是指 list 的倒数第二个元素，其他的以此类推。 通过切片访问，就要知道切片的书写格式： [start🔚det] 参数含义：start 表示起点， end 表示终点， det 表示访问时下标每次的增量，即步长。 如果 det 值为 1 ，那么实际上就是获取 list 对象中，下标在 [start, end) 之间的所有元素(注意，这是数学上的左闭右开区间)。 对于 det 属于任意非 0 整数的情况，实际上就是获取 list 对象中，下标分别是start start+det start+det2 …… start+deti的元素，构成的新列表。其中 |start+det*i| < |end| ，且 i∈N ，注意双竖线 || 表示取里面的绝对值，因为考虑到负数下标的问题。 和一些高级编程语言中，函数的参数列表中的默认参数类似，这里的变量也有默认值。默认情况下 start 是 0 ， end 是整个 list 的长度， det 是 1 。所以我们也应该遵守相关使用默认参数的规则，如果某一个参数不使用默认参数，那么其前面的参数，也都不是之前所说的默认值，所以在 Python 中表现就是，可以只用 1 个冒号，也可以用 2 个冒号。

输出： [1, 2, 3] 1 2 3 1 2 3 [1, 2, 3] [3, 2, 1] 如何“弹出” list 的第一个和最后一个元素 先不谈 list 的内置方法，结合之前学过的 list 的访问，我们最先想到的可能就是，先取到指定位置元素的值，然后再通过 del 方法，删除该位置上的元素。 示例如下：

输出： [1, 2, 3] 1 [2, 3] 很明显，过程比较麻烦，需要先取再删。而在我们学习编程和数据结构的过程，会发现很多高级编程语言都会有 pop 函数，这个函数就是用来完成上述功能。 同样的，Python 中 list 对象也为我们内置了 pop 函数。其接收一个整数，表示需要获取的元素的下标，且支持负数下标，不使用参数，则默认弹出最后一个元素。 示例如下：

输出： [1, 2, 3] 3 [1, 2] 1 [2] 如何向 list 添加数据 我们先在 ipython 的命令行窗口，看看 list 到底有哪些函数可以为我们所用。 list对象的方法 看了上图，大家可以尝试猜一下这些函数的功能。上图中 list 的这些函数，在很多其他高级编程语言都有类似函数，可以说是非常通用且强大。这里，从英语上来说， append 和 extend 都具有“添加”的意思，那为什么要分两个呢？让我们先来实验一下。 示例如下：

输出： [1, 2, 3] [1, 2, 3, [4, 5, 6]] [1, 2, 3, [4, 5, 6], 4, 5, 6] 通过上述例子可以看到， append 函数是把参数直接原封不动地添加到 ls 对象的尾部，而 extend 函数是把参数中的元素提取出来，然后再添加到 ls 对象的尾部，所以大家在用的时候，要视情况选择正确的函数。 更简便的是，与一些高级编程语言中的运算符重载类似，python 中 list 对象之间的 + 操作，可以实现类似 extend 函数的功能。 示例如下：

输出： [1, 2, 3] [1, 2, 3, 4, 5, 6] 编程要求 根据提示，在右侧编辑器 Begin-End 区间补充代码，先将输入的 list 添加4,5,6 3个元素，再添加元素 [7,8,9]，计算并输出修改后的 list ，及其第一个和最后一个元素。 测试说明 本关的测试文件是 src/step1/hello_world_stu.py 。 读者将 src/step1/hello_world_stu.py 中的代码补充完毕，然后点击评测，平台自动编译运行 src/step1/hello_world_stu.py ，并以标准输入方式提供测评输入； 平台获取程序的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。 平台会对你编写的代码进行测试： 测试输入： 1,2,3,4,5 预期输出： [1, 2, 3, 4, 5, 4, 5, 6, [7, 8, 9]] 1 [7, 8, 9] 开始你的任务吧，祝你成功！ 参考代码：

第2关：用Python实现简单的栈 任务描述 本关任务：编写一个栈。 相关知识 为了完成本关任务，你需要掌握： 栈的基本操作； Python 面向对象编程。 栈的基本操作 栈（ Stack ）又名堆栈，它是一种运算受限的线性表。 其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。 向一个栈插入新元素，又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素； 从一个栈删除元素，又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 栈元素的出入特点是先入后出或后入先出（FILO—first in last out）。 一开始需要声明栈的大小 size ，栈有一个 top 指针，始终指向栈顶元素，空栈 top 值为 -1 。 当栈没有满时，可以在栈顶进行压栈操作； 当栈不空时，可以将栈顶元素弹出，即出栈操作。 上述过程可由下图表示： 面向对象编程 编写一个我们自定义的栈，往往我们希望它能像 list 、 dict 等类型一样，可以通过类型名，去创建一个对象，并且可以调用其内部的出栈、入栈等操作的函数。所以我们需要了解在 Python 中，类的创建和一些基本函数的含义。 以创建具有学生姓名和年龄的学生类为例，示例如下：

输出： Name: Zhang Age: 15 从上述实例程序及输出，我们可以发现，Python 中创建的类是通过 class 关键字引出。当实例化一个自定义类时，将参数通过构造函数 __init__ ，赋值给成员变量，且成员变量是通过将 self. 作为前缀引出。Python 中类的方法的第一个参数始终是 self ，在外部实例调用其方法时，不需要考虑 self 这一位置上的参数，因为默认就是实例本身。 __repr__ 是 Python 中一个十分常用的函数，当实例作为 print 函数的参数时，就会输出实例的 __repr__的返回值，这也是我们这里有上述输出的原因。读者可以试下，如果不重写这个函数会输出什么。 编程要求 根据提示，在右侧编辑器 Begin-End 区间补充代码，实现栈的入栈( push )和出栈( pop )函数。要求如下： 入栈函数在栈满时，不进行操作；当有元素入栈时，将元素入栈，并且 top 进行加 1； 出栈函数在栈空时，不进行操作；当调用出栈函数时，将栈顶元素从栈中删除，并且将栈顶元素作为返回值返回。 测试说明 本关的测试文件是 src/step2/main.py 。 读者将 src/step2/stack_stu.py 中的代码补充完毕，然后点击评测，平台自动编译运行 src/step2/main.py ，并以标准输入方式提供测评输入； 平台获取程序的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。 平台会对你编写的代码进行测试： 第一行表示操作次数 n，接下来有 n 行输入，每一行有一个字符串，有可能有一个数字，如果字符串是 push ，那么后面有一个数字 x ，表示将 x 入栈，如果字符串是 pop ，那么后面没数字，表示将栈顶元素出栈。 输出 n 行，表示 n 次操作后对应的结果，当操作不合法时，需要禁止本次操作，并输出上一状态的栈序列。 测试输入： 5 push 3 push 4 pop push 1 pop 预期输出： [3] [3, 4] [3] [3, 1] [3] 开始你的任务吧，祝你成功！ 参考代码:

第3关：用Python实现简单的队列 任务描述 本关任务：编写一个简单的队列。 相关知识 为了完成本关任务，你需要掌握： 队列的基本操作； Python面向对象编程。 队列的基本操作 队列（ Queue ）是一种特殊的线性表，特殊之处在于，它只允许在表的前端（ front ）进行删除操作，即出队。而在表的后端（ rear ）进行插入操作，即入队。 和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队首。 队列元素的出入特点是先入先出或后入后出（FIFO—first in first out）。 一开始需要声明队列的大小 size ，队列有一个 front 指针和一个 rear ，分别指向队首元素和队尾元素。 当队列没有满时，可以在队尾进行入队操作； 当队列不空时，可以将队首元素弹出，即出队操作。 上述过程可由下图表示： 面向对象编程 此处请参照第二关面向对象编程的内容。 编程要求 根据提示，在右侧编辑器 Begin-End 区间补充代码，实现栈的入队(en_queue)和出队(de_queue)函数。 入队函数在队列满时，不进行操作；否则，当有元素入队时，将元素放置队尾，对应的 rear 进行加 1； 出队函数在队列空时，不进行操作；否则，当调用出队函数时，将队首元素从队列中删除，对应的 front 进行加 1，并且将队首元素作为返回值返回。 测试说明 本关的测试文件是 src/step3/main.py。 读者将 src/step3/queue_stu.py 中的代码补充完毕，然后点击评测，平台自动编译运行 src/step3/main.py，并以标准输入方式提供测评输入； 平台获取程序的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。 平台会对你编写的代码进行测试： 第一行表示操作次数 n ，接下来有 n 行输入，每一行有一个字符串，有可能有一个数字，如果字符串是 enQueue ，那么后面有一个数字 x ，表示将 x 入队，如果字符串是 deQueue，那么后面没数字，表示将队首元素出队。 输出 n 行，表示 n 次操作后对应的结果，当操作不合法时需要禁止本次操作，并输出上一状态的队列序列。 测试输入： 5 enQueue 3 enQueue 4 deQueue enQueue 1 deQueue 预期输出： [3] [3, 4] [4] [4, 1] [1] 开始你的任务吧，祝你成功！ 参考代码:

第4关：栈在括号匹配中的应用 任务描述 本关任务：给定一个只包括’(’，’)’，’{’，’}’，’[’，’]'的字符串，判断字符串是否有效。 相关知识 栈在括号表达式中的应用 问题分析 假设有以下括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 当处理第 1 个括号[时，期待与第 8 个括号]匹配； 当处理第 2 个括号(时，更加急切地期待与第 7 个括号)匹配，此时第 1 个括号[暂时放在一边； 当处理第 3 个括号[时，更加急切地期待与第 4 个括号]匹配，此时第 2 个括号(暂时放在一边。当第 3 个括号的期待得到满足，消解之后，第 2 个括号的期待匹配，又成为当前最急迫的任务了； 以此类推，可以发现处理过程和栈的思想相似。 算法思想 初始化一个空栈，顺序读入括号； 如果处理的是右括号，则尝试将栈顶元素与之进行括号匹配，若成功，则消除栈顶元素，否则，括号匹配失败； 如果处理的是左括号，则把这个括号当做当前最为急迫期待的元素压入栈顶； 处理完所有括号后，栈不为空，则括号不匹配，否则，括号匹配。 编程要求 根据提示，在右侧编辑器 Begin-End 区间补充代码，判断输入的字符串 s 是否合法，如果合法，则返回 True ，否则返回 False。 有效字符串需满足： 左括号必须用相同类型的右括号闭合； 左括号必须以正确的顺序闭合； 注意空字符串可被认为是有效字符串。 测试说明 本关的测试文件是src/step4/main.py。 读者将 src/step4/kuohao.py 中的代码补充完毕，然后点击评测，平台自动编译运行 src/step4/main.py，并以标准输入方式提供测评输入； 平台获取程序的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。 平台会对你编写的代码进行测试： 测试输入： [()] 预期输出： True 测试输入： ([)] 预期输出： False 开始你的任务吧，祝你成功！ 参考代码：

第5关：栈在表达式求值中的应用 任务描述 本关任务：编写一个能根据逆波兰表示法，求表达式的值的程序。 相关知识 为了完成本关任务，你需要掌握： 什么是逆波兰表达式； 栈和表达式求值的关系。 逆波兰表达式（Reverse Polish notation，RPN） 逆波兰表达式又叫做后缀表达式，是一种表示表达式的方法，按此方法，可以将每一运算符都置于其运算对象之后，故称为后缀表示。 例如，中缀表达式(a+b)c-(a+b)/e对应的的后缀表达式为ab+cab+e/-。 定义 一个表达式E的后缀形式可以如下定义： 如果E是一个变量或常量，则E的后缀式是E本身； 如果E是E1 op E2形式的表达式，这里op是二元操作符，则E的后缀式为E1’ E2’ op，这里E1’和E2’分别为E1和E2的后缀式； 如果E是E1形式的表达式，则E1的后缀式就是E的后缀式。 如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+ (a+b)c-(a+b)/e转化成后缀表达式的过程： (a+b)c-(a+b)/e →((a+b)c)((a+b)/e)- →((a+b)c)((a+b)e/)- →(ab+c)(ab+e/)- →ab+cab+e/- 为什么要将看似简单的中序表达式转换为复杂的逆波兰式？ 因为中序表达式的简单是相对人类的思维结构来说的，对计算机而言，中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来，却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。 栈和表示式求值 算法思想： 顺序扫描表达式的每一项，如果该项是操作数，则将其直接压入栈中； 如果该项是运算符op，则连续从栈弹出 2 个操作数X和Y，并将X和Y关于op的运算结果入栈； 全部处理后，栈顶元素就是最终表达式的值。 编程要求 根据提示，在右侧编辑器 Begin-End 区间补充代码，计算并返回指定逆波兰表达式的值。 说明： 整数除法只保留整数部分； 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值，且不存在除数为 0 的情况； 有效的运算符包括 +, -, *, /。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 测试说明 本关的测试文件是src/step5/main.py。 读者将 src/step5/expression_value_stu.py 中的代码补充完毕，然后点击评测，平台自动编译运行 src/step5/main.py，并以标准输入方式提供测评输入； 平台获取程序的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。 平台会对你编写的代码进行测试： 测试输入： [“2”, “1”, “+”, “3”, “*”] 预期输出： 9 提示： ((2 + 1) * 3) = 9 开始你的任务吧，祝你成功！ 参考代码：

第6关：栈在递归中的应用 任务描述 本关任务：编写一个能计算二叉树后序遍历的程序。 相关知识 为了完成本关任务，你需要掌握： 二叉树的后序遍历； 将递归函数通过栈改写成非递归函数。 二叉树的后序遍历 定义 后序遍历（ Postorder Traversal ，LRD ）是二叉树遍历的一种，也叫做后根遍历、后序周游。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根。巧记：左右根。 算法描述 后序遍历，首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即： 若二叉树为空，则结束返回； 否则： 后序遍历左子树； 后序遍历右子树； 访问根结点。 二叉树 如上图二叉树，其后序遍历结果为DEBFCA 注意 已知前序遍历和中序遍历，能唯一确定后序遍历； 已知后序遍历和中序遍历，能唯一确定前序遍历； 已知前序遍历和后序遍历，不能唯一确定中序遍历。 递归算法实现 假设树的结构为：

很容易写出其后序遍历的递归算法。

尽管二叉树后序遍历的递归算法显得十分简洁，但他有许多不可忽视的缺点： 由于递归是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中，分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间； 递归中，很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算，如斐波那契数列的递归实现； 调用栈可能会溢出，其实每一次函数调用，会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。 所以，诸如解决斐波那契数列相似问题，在数据量一大的情况下，递归的效率就十分的不友好。因此，掌握常用算法的非递归算法，也是我们应该具有的一个能力！ 将递归函数通过栈改写成非递归函数 以求解第 n 项斐波那契数为例，很容易写出其递归程序：

第8关：关于栈和队列的一些习题 栈和队列是贯穿整个数据结构的两个非常重要的数据结构，希望大家能通过编程对其有初步的认识，现在请读者根据之前的学习完成一些选择题。 参考答案: